package com.maltys.backtracking;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author maltys
 * @link <a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/">...</a>
 */
public class PhoneNumberCombine {
    public static void main(String[] args) {
        PhoneNumberCombine phoneNumberCombine = new PhoneNumberCombine();
        List<String> strings = phoneNumberCombine.letterCombinations("6");
        System.out.println(strings);
    }

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.isEmpty()) {
            return res;
        }

        Map<Integer, String> digitsMap = new HashMap<>(9);
        digitsMap.put(2, "abc");
        digitsMap.put(3, "def");
        digitsMap.put(4, "ghi");
        digitsMap.put(5, "jkl");
        digitsMap.put(6, "mno");
        digitsMap.put(7, "pqrs");
        digitsMap.put(8, "tuv");
        digitsMap.put(9, "wxyz");

        backTracing(digits, 0, new StringBuilder(), digitsMap, res);
        return res;
    }

    private void backTracing(String digits, int idx, StringBuilder sb, Map<Integer, String> digitsMap, List<String> res) {
        if (idx == digits.length() && sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }

        if (idx > digits.length() || sb.length() > digits.length()) {
            return;
        }

        for (int i = idx; i < digits.length(); i++) {
            int digit = digits.charAt(i) - '0';
            String chars = digitsMap.get(digit);
            for (int j = 0; j < chars.length(); j++) {
                sb.append(chars.charAt(j));
                backTracing(digits, i + 1, sb, digitsMap, res);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }
}
